package com.itheima.leetcode.od.c.graph;

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * <h3>可以处理的最大任务数（超时版）</h3>
 */
public class MaximumOfProcessbleTasks1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        // 结束时间越大（越晚）优先级越高，结束时间相同时，开始时间越大（越晚）优先级越高
        PriorityQueue<Range> pq =
                new PriorityQueue<>((a, b) -> a.end != b.end ? b.end - a.end : b.start - a.start);

        for (int i = 0; i < n; i++) {
            pq.offer(new Range(sc.nextInt(), sc.nextInt()));
        }

        // 记录最大任务数
        int count = 0;

        // 记录上一个任务的执行时刻
        int last_end = Integer.MAX_VALUE;

        while (pq.size() > 0) {
            Range range = pq.poll();

            if (range.end < last_end) {
                // 当前任务结束时刻end < 上个任务结束时刻last_end，则当前任务选择在end时刻执行
                last_end = range.end;
                count++;
            } else if (last_end > range.start) {
                // 当前任务结束时刻end ≥ 上个任务结束时刻last_end，则更新当前任务的结束时间为last_end-1，后重新加入优先队列排队
                // 同时注意range新的结束时间last_end - 1不能小于range.start，否则该任务无法执行
                range.end = last_end - 1;
                pq.offer(range);
            }
        }

        System.out.println(count);
    }

    static class Range {
        int start;

        int end;

        public Range(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}